package com.ztl.example.sorts;

/**
 * @author @ztl
 * @ClassName:InsertionSort
 * @Package:com.ztl.example.sorts
 * @date 2023年06月01日 20:38
 * @description:插入排序 时间复杂度O(n^2) 空间复杂度O(1)
 * @version: 1.0
 */
public class InsertionSort {
    public static void  insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) { //从第二个元素开始插入
            for (int j = i; j > 0; j--) {   //从i开始对比寻找插入位置
                if (arr[j] < arr[j - 1]) {//符合条件，插入元素（交换位置）
                    int temp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = temp;
                }
            }
        }
    }
}
